package fpTree;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import stats.FpTreeStats;

import mining.CsvReader;
import mining.ItemSetMining;
import mining.WriteStats;

public class FpTree extends ItemSetMining
{
	
	// whether to split tree into single prefix path during mining
	private final boolean rare;
	private BufferedWriter bw;
	// public Node root;
	private final static boolean write = false;
	
	FpTreeStats stats;
	
	public FpTree(String filePath, boolean rare)
	{
		super(filePath);
		
		this.stats = new FpTreeStats();
		this.stats.className = this.getClass().getSimpleName();
		this.stats.write = write;
		this.stats.location = filePath;
		
		this.rare = rare;
	}
	
	public void run()
	{
		if (write)
		{
			this.bw = null;
			try
			{
				this.filename = this.filePath + "-" + this.getMinRareItemsetSupport() + "-"
				+ this.getMinFreqItemsetSupport() + "-" + this.getClass().getSimpleName();
				this.bw = new BufferedWriter(new FileWriter(this.filename));
			} catch (IOException e)
			{
				e.printStackTrace();
			}
		}

		//		System.out.println("Running: " + this.getClass().getSimpleName());
//		System.out.println("minRareSup: " + this.getMinRareItemsetSupport()
//				+ " | minFreqSup: " + this.getMinFreqItemsetSupport());
		
		this.stats.minRareItemsetSup = this.getMinRareItemsetSupport();
		this.stats.minFreqItemsetSup = this.getMinFreqItemsetSupport();
		
		// start timing
		long t1 = System.nanoTime();
		
		Node root = new Node();
		// this.root = root;
		
		Map<Integer, Node> headerTableLast = new HashMap<Integer, Node>();
		
		Map<Integer, Integer> itemFreqs = countItemSupport();
		List<Integer> fList = createFList(itemFreqs);
		this.stats.iterations = fList.size();
//		System.out.println("fList " + fList.size() + ": " + fList);
		// System.out.println("itemFreqs: " + itemFreqs);
		
		Map<Integer, Node> headerTable = new LinkedHashMap<Integer, Node>();
		initialiseLinkedHashMap(headerTable, fList);
		
		Map<Integer, Integer> fListMap = listToMap(fList);
		for (CsvReader reader = new CsvReader(this.filePath); reader.hasNext();)
		{
			List<Integer> transaction = new ArrayList<Integer>(reader.read());
			processTransaction(transaction, 1, root, headerTable, headerTableLast, fListMap);
		}
		
//		System.out.println(root.printTree());
		
//		System.out.println("headerTable keySet() " + headerTable.keySet().size() + ": " + headerTable.keySet());
		multiPath(headerTable, Collections.<Integer> emptySet(), root, "");
		
		if (write)
		{
			try
			{
				this.bw.close();
			} catch (IOException e)
			{
				e.printStackTrace();
			}
		}
		
//		System.out.println("iteration itemset sizes: " + this.numIterationItemsets);
//		System.out.println("number if items in all itemsets: " + this.numItemsetItems);
//		System.out.println("result size: " + this.lineCount);
		
		long t2 = System.nanoTime();
		this.stats.runtime = (t2 - t1) / 1000000;
		
		System.out.println(this.stats);
		WriteStats.write(this.stats);
	}
	
	/**
	 * Creates list of items ordered by decreasing frequency. 
	 */
	private List<Integer> createFList(Map<Integer, Integer> itemFreqs)
	{
		List<Integer> fList = new ArrayList<Integer>();
		
		int itemsetSupport;
		if (this.rare)
			itemsetSupport = getMinRareItemsetSupport();
		else
			itemsetSupport = getMinFreqItemsetSupport();
		for (int itemName : itemFreqs.keySet())
		{
			// if looking for rare items, then set threshold to the lower minRareItemsetSupport
			if (itemFreqs.get(itemName) >= itemsetSupport)
			{
				fList.add(itemName);
			}
		}
		Collections.sort(fList, new FListComparator(itemFreqs));
		
		return fList;
	}
	
	/**
	 * Sets up the iteration order of the LinkedHashMap to be the reverse of <tt>fList</tt>,
	 * i.e. increasing frequency.
	 * 
	 * @param headerTable
	 * @param fList
	 */
	private void initialiseLinkedHashMap(Map<Integer, Node> headerTable, List<Integer> fList)
	{
//		System.out.println("initHashMap: " + fList);
		for (int i = fList.size() - 1; i >= 0; i--)
		{
			headerTable.put(fList.get(i), null);
		}
	}
	
	// returns header table of generated fptree
	
	/**
	 * @param fList
	 *            - the list of itemNames ordered by decreasing frequency order. The <i>reverse</i> order of this list is the iteration
	 *            order of the returned Header Table. This list is not modified.
	 * @param root
	 *            - the Node that will be the root of the new FP-Tree. This object is modified within the method.
	 * @param transactions
	 *            - a <tt>Map</tt> containing transactions and their frequencies that are to be added to the FP-Tree.
	 * @return a Header Table of the new FP-Tree created from the transactions
	 */
	private Map<Integer, Node> processTransactions(Map<List<Integer>, Integer> transactions, final List<Integer> fList, Node root)
	{
		// Node root = new Node(); // use the root provided
		
		Map<Integer, Node> headerTable = new LinkedHashMap<Integer, Node>();
		// ensuring the order of iteration will be the reverse order of fList
		initialiseLinkedHashMap(headerTable, fList);
		
//		System.out.println(headerTable.keySet());
		
		// testing
		// ArrayList<Integer> testArray = new ArrayList<Integer>(fList);
		// Collections.reverse(testArray);
		// assert(testArray.equals(new
		// ArrayList<Integer>(headerTable.keySet()))) :
		// "Order is not reversed.";
		
		Map<Integer, Node> headerTableLast = new HashMap<Integer, Node>();
		Map<Integer, Integer> fListMap = listToMap(fList);
		
		for (List<Integer> transaction : transactions.keySet())
		{
			processTransaction(transaction, transactions.get(transaction), root, headerTable, headerTableLast, fListMap);
		}
		
		return headerTable;
	}
	
	private Map<Integer, Integer> listToMap(List<Integer> list)
	{
		Map<Integer, Integer> fListMap = new HashMap<Integer, Integer>();
		for (int i = 0; i < list.size(); i++)
		{
			fListMap.put(list.get(i), i);
		}
		return fListMap;
	}
	
	/**
	 * Adds a transaction to an existing FP-Tree (that may just be a root node). Items in the transaction that are below minimum support
	 * (i.e. not in <tt>fList</tt>) are removed
	 * 
	 * @param <tt>headerTableLast</tt> used by processTransaction only, to keep track of the last node in each of the series of Nodes in
	 *        <tt>headerTable</tt> (i.e. Nodes that were first placed into <tt>headerTable</tt>).
	 */
	private void processTransaction(List<Integer> transaction, int frequency, Node root,
									Map<Integer, Node> headerTable, Map<Integer, Node> headerTableLast,
									final Map<Integer, Integer> fListMap)
	{
		removeItemsBelowSupport(transaction, fListMap.keySet());
		
		// sort the transaction according to order in fList(fListMap)
		// System.out.println("unsorted: " + transaction);
		Collections.sort(transaction, new Comparator<Integer>()
		{
			@Override
			public int compare(Integer s1, Integer s2)
			{
				return fListMap.get(s1) - fListMap.get(s2);
			}
		}); // sort items in this transaction
		
		Node current = root;
		for (int item : transaction)
		{
			// look for the right child to increment, if one exists
			if (current.getChildren().containsKey(item))
			{ // if child exists, increment count
				current = current.getChildren().get(item); 
				current.setCount(current.getCount() + frequency);
			} else
			{ // if it does not, create a child
				Node nn = new Node();
				nn.itemName = item;
				nn.setCount(frequency); // initialise count
				current.getChildren().put(item, nn); // add new node to parent
				nn.parent = current; // add parent to new node
				
				// add node-link
				// headerTable.get(string).add(nn);
				
				// have to test with null and not containsKey because
				// headerTable has been initialised
				if (headerTable.get(item) == null)
				{
					// System.out.println("adding first");
					headerTable.put(item, nn);
				}
				if (!headerTableLast.containsKey(item))
				{
					headerTableLast.put(item, nn);
				} else
				{
					headerTableLast.put(item, nn).setNodeLink(nn);
				}
				
				current = nn;
			}
		}
	}
	
	// remove items not in fList (i.e. below minSup)
	private void removeItemsBelowSupport(List<Integer> transaction, final Collection<Integer> fList)
	{
		for (Iterator<Integer> i = transaction.iterator(); i.hasNext();)
		{
			int s = i.next();
			if (!fList.contains(s))
			{
				i.remove();
			}
		}
	}
	
//	List<Long> numIterationItemsets = new ArrayList<Long>();
	long iterationItemsetCount = 0;
	
//	long numItemsetItems;
	private void multiPath(Map<Integer, Node> headerTable, final Set<Integer> alpha, Node root, String spacing)
	{
		spacing = "@" + spacing + " ";
		
		// System.out.println(spacing + "tree conditional on " + alpha + ": ");
		// System.out.println(root.printTree());
		for (int itemName : headerTable.keySet())
		{ // for each item in Q... i.e. branching part
		
			if (alpha.isEmpty())
			{
				this.iterationItemsetCount = 0;
			}
			
			final Set<Integer> freqPatternQ = new LinkedHashSet<Integer>(alpha);
			freqPatternQ.add(itemName); // beta = ai UNION alpha (line 10)
			
			Node newRoot = new Node();
			Node firstNodeLink = headerTable.get(itemName);
			Map<Integer, Node> newHeaderTable = constructConditional(firstNodeLink, spacing, newRoot);
			
			// System.out.println("newHeaderTable: " + newHeaderTable);
			// System.out.println("itemName tally " + itemName + ": " +
			// tallyNodeLinkCount(headerTable.get(itemName)));
			multiPath(newHeaderTable, freqPatternQ, newRoot, spacing);
			
			int tally = tallyNodeLinkCount(firstNodeLink);
			if (this.rare)
			{
				if (tally < this.getMinFreqItemsetSupport())
				{
					this.iterationItemsetCount++;
					this.stats.numItemsets++;
					this.stats.numItemsetItems += freqPatternQ.size();
					writeToFile(freqPatternQ, tally);
				}
			} else
			{
				this.iterationItemsetCount++;
				this.stats.numItemsetItems += freqPatternQ.size();
				this.stats.numItemsets++;
				writeToFile(freqPatternQ, tally);
			}
			
			if (alpha.isEmpty())
			{
//				System.out.println(itemName + " | " + this.iterationItemsetCount);
				this.stats.numIterationItemsets.add(this.iterationItemsetCount);
			}
			
		}
	}
	
	int fileNum;
	private void writeToFile(Set<Integer> itemset, int support)
	{
		if (!write)
			return; 
		
		try
		{
			if (this.stats.numItemsets % (1 << 22) == 0)
			{
				this.fileNum++;
				this.bw.close();
				this.bw = new BufferedWriter(new FileWriter(this.filename + "." + this.fileNum));
			}
			this.bw.write(itemset.toString());
			this.bw.write(",");
			this.bw.write(Integer.toString(support));
			this.bw.newLine();
		} catch (IOException e)
		{
			e.printStackTrace();
		}
	}
	
	// add up the frequencies of the nodes linked together by NodeLink
	private int tallyNodeLinkCount(Node node)
	{
		int count = 0;
		for (Node temp = node; temp != null; count += temp.getCount(), temp = temp.getNodeLink())
			;
		return count;
	}
	
	/**
	 * Constructs a conditional FP-Tree using a series of <tt>Node</tt> objects that begins with <tt>firstNode</tt>, and connected together
	 * by <tt>nodeLink</tt>. The conditional tree does not include the item represented by the firstNode. The returned Header Table is of
	 * the constructed conditional FP-Tree.
	 * 
	 * @param root
	 *            - the Node that will be used as the root of the new FP-Tree that is constructed
	 * @param firstNode
	 *            - the first <tt>Node</tt> in a series of nodes
	 * @return the Header Table of the conditional FP-tree that is constructed
	 * 
	 */
	private Map<Integer, Node> constructConditional(final Node firstNode, String spacing, Node root)
	{
		
//		printing node links
//		Node temp = firstNode;
//		StringBuilder sb = new StringBuilder();
//		int i = 0;
//		while (temp != null) {
//			i++;
//			sb.append(temp + " ");
//			temp = temp.nodeLink;
//		}
//		System.out.println("Node links " + i + ": " + sb.toString());
		
		// make conditional pattern base, and count item frequencies
		Map<List<Integer>, Integer> conditionalPatterns = new HashMap<List<Integer>, Integer>();
		Map<Integer, Integer> freqs = new HashMap<Integer, Integer>(); // for storing 1-itemset frequencies
		
		Node linkNode;
		for (linkNode = firstNode; linkNode != null; linkNode = linkNode.getNodeLink())
		{
			
			// build pattern by going up parents
			LinkedList<Integer> pattern = new LinkedList<Integer>(); // stores one conditional pattern
			
			Node parentNode = linkNode.parent; // don't include the current node in the header table
			while (parentNode != null && parentNode.itemName != -1)
			{
				
				// counting 1-itemset frequencies by going thorugh through link
				// nodes and their parents
				if (!freqs.containsKey(parentNode.itemName))
				{
					freqs.put(parentNode.itemName, linkNode.getCount());
				} else
				{
					freqs.put(parentNode.itemName, freqs.get(parentNode.itemName) + linkNode.getCount());
				}
				pattern.addFirst(parentNode.itemName);
				parentNode = parentNode.parent;
			}
			
			if (!pattern.isEmpty())
				conditionalPatterns.put(pattern, linkNode.getCount()); // add pattern to pattern-base
			
		}
		
		// newFList contains only item names that have over the required support
		List<Integer> newFList = createFList(freqs);
		
		// System.out.println("conditionalPatterns: " + conditionalPatterns);
		// System.out.println();
		
//		System.out.println("alpha: " + firstNode.itemName);
//		System.out.println(spacing + " conditional patterns: " + conditionalPatterns);
		
		// build the tree using transactions
		if (!conditionalPatterns.isEmpty())
		{
//			Map<Integer, ExtNode> newHeaderTable = processTransactions(conditionalPatterns, newFList, root);
//			return newHeaderTable;
			return processTransactions(conditionalPatterns, newFList, root);
		} else
		{
			return Collections.emptyMap();
		}
	}
}
